You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given: s: "barfoothefoobarman" words: ["foo", "bar"]

You should return the indices: [0,9]. (order does not matter).



In [10]:

    
class Solution(object):
    def findSubstring(self, s, words):
        """
        每次判断单词是否在words_set里面
        需要注意的是bar的出现的次数比在words中多
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        words_set = {}
        word_num = len(words)
        for word in words:
            if word not in words_set:
                words_set[word] = 1
            else:
                words_set[word] += 1
        word_len = len(words[0])
        res = []
        for i in range(len(s)+1-word_len * word_num):
            curr, j = {}, 0
            while j < word_num:
                word = s[i+j*word_len: i + j*word_len + word_len]
                if word not in words_set:
                    break
                if word not in curr:
                    curr[word] = 1
                else:
                    curr[word] += 1
                if curr[word] > words_set[word]: break
                j+=1
            if j == word_num:
                res.append(i)
        return res



In [11]:

    
Solution().findSubstring("barfoothefoobarman", ["foo", "bar"])









    Out[11]:





[0, 9]



In [3]:

    
def all_sorted(s):
    if len(s) == 1:
        return s[0]
    else:
        return s[0]+all_sorted(s[1:])



In [4]:

    
all_sorted(["foo", "bar"])









    Out[4]:





'foobar'



In [ ]: